package com.gitee.wsl.ext.array

import com.gitee.wsl.collections.list.LinkedList
import com.gitee.wsl.ext.base.Arrays.arraycopy
import com.gitee.wsl.ext.list.peek
import com.gitee.wsl.ext.list.pop


private fun mergeSort(array: IntArray, low: Int, high: Int) {
    if (array.isEmpty()) {
        return
    }
    // WARNING: if statement and not while
    if (low < high) {
        val mid = (low + high) / 2
        // break left
        mergeSort(array, low, mid)
        // break right
        mergeSort(array, mid + 1, high)
        // sort and merge
        kSortedListMerge(array, low, high, mid)
    }
}

fun kSortedListMerge(array: IntArray, low: Int, high: Int, mid: Int) {
    val queue1 = LinkedList<Int>()
    val queue2 = LinkedList<Int>()
    for (i in low..mid) {
        queue1.add(array[i])
    }
    for (i in mid + 1..high) {
        queue2.add(array[i])
    }

    var i = low
    // do till one of them is empty
    while (queue1.isNotEmpty() && queue2.isNotEmpty()) {
        // pick the smallest of item; which is at head since at last level, only 1 item remains
        if (queue1.peek() < queue2.peek()) {
            array[i] = queue1.pop()
        } else {
            array[i] = queue2.pop()
        }
        i++
    }

    // Remaining items in queue1
    while (queue1.isNotEmpty()) {
        array[i] = queue1.pop()
        i++
    }
    // Remaining items in queue2
    while (queue2.isNotEmpty()) {
        array[i] = queue2.pop()
        i++
    }
}

/**
 * Merge sort is an efficient, stable, and comparison-based sorting algorithm.
 * It works by dividing the unsorted list into n sublists, each containing one element,
 * and then repeatedly merging sublists to produce new sorted sublists until there is only one sublist remaining.
 *
 * Invented in 1945 by John von Neumann, merge sort is an efficient algorithm using the divide and conquer approach
 * which is to divide a big problem into smaller problems and solve them. Conceptually, a merge sort works as follows:
 * 1) Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
 * 2) Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining.
 *
 * Worst-case performance:       O(n log n)
 * Best-case performance:        O(n log n)
 * Average performance:          O(n log n)
 * Worst-case space complexity:  O(n)
 */
fun<T : Comparable<T>> Array<T>.mergeSort(){
    val aux = clone()
    sort(this, aux, 0, size - 1)
}


/**
 * Recursively sorts the array using merge sort.
 *
 * @param arr The array to sort.
 * @param aux The auxiliary array used for merging.
 * @param low The low index of the current range.
 * @param high The high index of the current range.
 * @param T The type of elements in the array, must be comparable.
 */
private fun <T : Comparable<T>> sort(
    arr: Array<T>,
    aux: Array<T>,
    low: Int,
    high: Int,
) {
    if (high <= low) {
        return
    }
    val mid = (low + high) / 2
    sort(arr, aux, low, mid)
    sort(arr, aux, mid + 1, high)
    merge(arr, aux, low, mid, high)
}

/**
 * Merges two sorted subarrays into a single sorted subarray.
 *
 * @param arr The array to sort.
 * @param aux The auxiliary array used for merging.
 * @param low The low index of the current range.
 * @param mid The mid-index of the current range.
 * @param high The high index of the current range.
 * @param T The type of elements in the array, must be comparable.
 */
private fun <T : Comparable<T>> merge(
    arr: Array<T>,
    aux: Array<T>,
    low: Int,
    mid: Int,
    high: Int,
) {
    arraycopy(arr, low, aux, low, high - low + 1)

    var i = low
    var j = mid + 1

    for (k in low..high) {
        when {
            i > mid -> arr[k] = aux[j++]
            j > high -> arr[k] = aux[i++]
            aux[j] < aux[i] -> arr[k] = aux[j++]
            else -> arr[k] = aux[i++]
        }
    }
}
